package demo9;

import java.util.*;

public class Test {

    public List<Integer> findSubstring(String s, String[] words)
    {
        List<Integer> ret = new ArrayList<Integer>();
        // 保存字典中所有单词的频次
        Map<String, Integer> hash1 = new HashMap<String, Integer>();
        for(String str : words) hash1.put(str, hash1.getOrDefault(str, 0) + 1);
        int len = words[0].length(), m = words.length;
        for(int i = 0; i < len; i++) // 执行次数
        {
            // 保存窗口内所有单词的频次
            Map<String, Integer> hash2 = new HashMap<String, Integer>();
            for(int left = i, right = i, count = 0; right + len <= s.length();right += len)
            {
                // 进窗口 + 维护 count
                String in = s.substring(right, right + len);
                hash2.put(in, hash2.getOrDefault(in, 0) + 1);
                if(hash2.get(in) <= hash1.getOrDefault(in, 0)) count++;
                // 判断
                if(right - left + 1 > len * m)
                {
                    // 出窗口 + 维护 count
                    String out = s.substring(left, left + len);
                    if(hash2.get(out) <= hash1.getOrDefault(out, 0)) count--;
                    hash2.put(out, hash2.get(out) - 1);
                    left += len;
                }
                // 更新结果
                if(count == m) ret.add(left);
            }
        }
        return ret;
    }
    //使用变量count维护有效字符的个数，hash1记录p的字符频率，hash2记录窗口内的字符频率
    public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        int count = 0; //记录有效字符的个数
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        int[] hash1 = new int[26];
        for (char ch : pp) {
            hash1[ch - 'a']++;
        }
        int[] hash2 = new int[26];
        int n = s.length(), m = p.length();
        for (int left = 0, right = 0; right < n; right++) {
            char in = ss[right];
            hash2[in - 'a']++; //入窗口
            if (hash2[in - 'a'] <= hash1[in - 'a']) count++; //维护count
            while (right - left + 1 > m) { //判断
                char out = ss[left];
                if (hash2[out - 'a'] <= hash1[out - 'a']) count--;
                hash2[out - 'a']--; //出窗口
                left++;
            }
            if (count == m) {
                ret.add(left);
            }
        }
        return ret;
    }

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        int[] hash1 = new int[26];
        for (char ch : pp) {
            hash1[ch - 'a']++;
        }
        int[] hash2 = new int[26];
        int n = s.length(), m = p.length();
        for (int left = 0, right = 0; right < n; right++) {
            char in = ss[right];
            hash2[in - 'a']++; //入窗口
            while (right - left + 1 > m) { //判断
                char out = ss[left];
                hash2[out - 'a']--; //出窗口
                left++;
            }
            if (Arrays.equals(hash1, hash2)) {
                ret.add(left);
            }
        }
        return ret;
    }
}
